In digital communications, bit errors may sometimes occur during data transmission. For example, an intended sequence of bits may be transmitted in a wired or wireless fashion, but when received, one or more of the bits may not be correctly received (e.g. a bit that was transmitted as a 0 is received as a 1). Since this is clearly an undesirable scenario, a variety of error detection and correction codes have been developed.
A simple known error detection technique is referred to as parity. Parity adds a single bit to a packet that indicates whether the number of ones (bit-positions with values of one) in the preceding data of the packet was even or odd. If an odd number of bits is changed in transmission, the message will change parity and the error is thus detected at this point; however, one drawback is that the bit that changed may have been the parity bit itself. The most common convention for the use of parity is that a parity value of one indicates that there is an odd number of ones in the data, and a parity value of zero indicates that there is an even number of ones in the data. If the number of bits changed is even, the check bit will be valid and the error will not be detected.
However, parity does not indicate which bit contained the error, even when it can detect the error. Once an error is detected using parity, the data must then be discarded entirely and re-transmitted from scratch. Over a noisy transmission medium, a successful re-transmission could take an undesirably long time, or may never in fact occur. Therefore, the overall quality and usefulness of parity checking on its own is poor. However, while the quality of parity checking is poor, since it uses only a single bit, this method results in minimal overhead, is simple to implement, and naturally, is better than no error checking.
Another known error detection technique is known as a two-out-of-five code. A two-out-of-five code is an encoding scheme which uses five bits—three zeroes and two ones. This provides ten possible combinations, enough to represent the digits 0-9. This scheme can therefore detect all single bit-errors, all odd numbered bit-errors, and some even numbered bit-errors (for example the flipping of both 1-bits). However, while this error detection technique can detect more errors than simple parity checking, it cannot correct any of the errors that it detects.
A known error detection and error correction technique is modular redundancy. With modular redundancy, every data bit is repeated multiple times in order to ensure that it was sent correctly. For instance, if the data bit to be sent is a 1, an n=3 repetition code will send 111. If the three bits received are not identical, an error occurred during transmission. If the transmission channel or medium is clean enough, most of the time only one bit will change in each triple. Therefore, 001, 010, and 100 each correspond to a 0 bit, while 110, 101, and 011 correspond to a 1 bit, as though the bits count as “votes” towards what the intended bit is. Since this code has the ability to reconstruct the original message in the presence of errors, it is known as an error-correcting code.
Such codes cannot correctly repair all errors, however. For example, if the channel flips two bits and the receiver receives 001, the system will detect the error, but conclude that the original bit is 0, which is incorrect. If the number of times each bit is duplicated is increased to four, all two-bit errors may be detected but correction is not possible, as the votes “tie”. At five repetitions for each bit, all two-bit errors can be corrected, but not all three-bit errors. Therefore, it can be seen that a modular repetition code is extremely inefficient, reducing throughput by a number of times equal to the number of repetitions used, and the efficiency drops drastically. This increases the number of times each bit is duplicated in order to detect and correct more errors.
Therefore, the development of a technique for detecting a large percentage of errors, while maintaining capability of correcting at least an acceptable percentage of errors, that does not utilize a large overhead, and that is not overly inefficient is needed.